package Top_Interview_Questions.Dynamic_Programming;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/4 12:02
 * <p>
 *  还有一些BFS的方法没看
 */
public class _0279 {

    public static void main(String[] args) {
        _0279 test = new _0279();
        test.numSquares(13);
    }

    /*---------------------------------------动态规划-----------------------------------------*/


    /**
     *   # dp[i]：表示完全平方数和为i的 最小个数
     *   # 初始状态dp[i]均取最大值i，即 1+1+...+1，i个1; dp[0] = 0
     *   # dp[i] = min(dp[i], dp[i-j*j]+1)，其中, j是平方数, j=1~k,其中k*k要保证 <= i
     *   # 意思就是：完全平方数和为i的 最小个数 等于 当前完全平方数和为i的 最大个数
     *   #   与 （完全平方数和为 i - j * j 的 最小个数 + 完全平方数和为 j * j的 最小个数）
     *   #   可以看到 dp[j*j] 是等于1的
     *
     *   也就是dp[1*1],dp[2*2],dp[3*3],dp[4*4]全都是1。后面不是平方数的就按i-j*j的差值所对应的数加1,比如
     *   dp[5]=Math.min(dp[i], dp[i - j * j] + 1)
     *   dp[5]=Math.min(dp[5], dp[5 - 2 * 2] + 1)
     *   dp[5]=Math.min(5, dp[1] + 1) -->按i-j*j的差值所对应的数加1,加的1表示前面的dp[j*j]是个完全平方数
     *
     *  https://leetcode-cn.com/problems/perfect-squares/solution/hua-jie-suan-fa-279-wan-quan-ping-fang-shu-by-guan/
     *
     */
    public int numSquares(int n) {
        int[] dp = new int[n + 1]; // 默认初始化值都为0
        for (int i = 1; i <= n; i++) {
            dp[i] = i; // 最坏的情况就是每次+1
            for (int j = 1; i - j * j >= 0; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 动态转移方程
            }
        }
        return dp[n];
    }


    /*-------------------------------------------------------------------------------------*/

}
